package zuoshen_mid.class2;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/* 
    得到n个节点的二叉树的节点个数
*/
public class NumberOfBTree {
    
    /* 
        复杂度分析：
        n时：left有0~n-1种取值 n * 1 + (n - 1) * 1  + (n - 2) * 2 + ... + n/2 * n/2
        n！级别问题
    */
    public int numOfTree(int n) {
        //0只有一个中形态
        if (n == 0) return 1;
        if (n == 1 || n == 2) return n;

        int res = 0;
        //左子树最少0个，最多n-1个(根节点必须有一个，且子树也可以为空)
        for (int left = 0; left < n; left++) {
            res += numOfTree(left) * numOfTree(n - left - 1);
        }
        return res;
    }

    /* 
        变化量：i
        变化范围：0 ~ n
        basecase: f[0] = f[1] = 1, f[2] = 2;
        表达式: f[n] = f[i] * f[n - i - 1]
    */
    public int numOfTree2(int n) {
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            //枚举left的范围
            /* 
                此时：
                i表示各个状态的n
                j表示n下各个大小的left
            */
            for (int j = 0; j < i; j++) {
                f[i] += f[j] * f[i - j - 1];
            }
        }
        return f[n];
    }

    @Test
    public void test1() {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            int res1 = numOfTree(i);
            int res2 = numOfTree2(i);
            if (res1 != res2) {
                System.out.println(i);
            } else {
                list.add(res1);

            }
        }
        System.out.println(list);
    }

    @Test
    public void test4() {
        int i = 0;
        while (true) {
            i++;
        }
    }
}
